1. Field of the Invention
The present invention relates to the field of image recognition, and in particular to a method and apparatus for accelerated handwritten symbol recognition in a pen based tablet computer.
2. Background Art
In some computer systems, handwritten symbols are input to the system. These symbols are translated by the computer system to machine readable characters. This translation is typically computation intensive. In some computer systems, battery operated portable devices for example, the general purpose central processing unit (CPU) used for the translation is inefficient in its power consumption during the translation operation. Thus, the battery is drained more rapidly. Additionally, some battery operated systems are limited in computational power. When a real-time translation requirement is placed on symbol translation, the limited computational power results in a limited degree of accuracy in the translation process. These problems can be better understood with a review of handwritten data entry.
Handwritten Data Entry
A typical computer system consists of a central processing unit (CPU), main memory such as random access memory (RAM), a data entry device, including a positioning device, a mass storage device such as one or more disk drives, a display and/or a printer. In the prior art, the data entry device often consists of a keyboard, on which a user enters data by typing. The positioning device of a prior art computer system may consist of a “mouse” or other cursor positioning device.
Computer systems also exist that are directed to handwritten data entry rather than keyboard data entry. These systems are often characterized by the use of a pen, stylus, or other writing device, to enter handwritten data directly on the display of the computer system. Alternatively, these systems may provide for a user to enter data on a digitizing tablet or other input device, with the image of the written input displayed on a separate computer display output device. The writing device for entering handwritten or freestyle stroke input information is not limited to a pen or stylus, but may be any input device such as a mouse, trackball, pointer, or even a person's fingers. Such systems are not necessarily limited to receiving data generated by human users. For example, machine generated data may also be inputted and accepted to such systems.
One class of this handwriting entry computer system that receives handwritten data input is referred to as a “pen based” computer system. In a pen based computer system, a writer can input information on a display by “writing” directly on the display. A writing device, such as a pen or stylus, is used to enter information on the display. In a typical pen-based computer system, a user touches the stylus to the display and writes as the user would on a piece of paper, by making a series of pen strokes to form letters and words. A line appears on the display that follows the path of travel of the pen point, so that the pen strokes appear on the display as ink would appear on a handwritten page. Thus, the user can enter information into the computer by writing on the display. Pen based computers typically have a display surface that serves as both an input receiving device and as an output display device.
Handwritten Data Translation
One characteristic of handwriting entry computer systems is the ability to translate original handwritten symbols into machine readable words or characters for display. This translation is accomplished via a “character recognition” algorithm. The handwritten symbols are translated into, for example, ASCII characters. After the translation, the appearance of the displayed characters is as if they had been typed in via a keyboard.
To translate a handwritten character into a machine readable character, the handwritten character is compared to a library of characters to determine if there is a match. A description, or “template” for each character is defined and stored in memory. Handwritten characters are compared to the stored templates. Match coefficients, reflecting how closely a handwritten character matches the template of a stored character, are calculated for each template character. The template character with the highest match coefficient is identified. The character represented by this template provides the “best fit” for the handwritten character. If the match coefficient for the “best fit” character exceeds a predetermined minimum threshold, the “best fit” character is adopted. If the match coefficient for the “best fit” character is less than the minimum threshold value, no translation is done. If the handwritten character cannot be translated, the character must be re-entered.
A disadvantage of current character recognition algorithms is limited accuracy. Often, handwritten characters are not translated at all or are mistranslated as an ASCII character other than the handwritten character. The mistranslated character must then be rewritten by the user, sometimes repeatedly, until a correct translation is made.
Handwriting Recognition in Portable Systems
A portable pen-based computer systems is constrained by the amount of power stored in its battery. Typically, portable pen-based computer systems, which require handwriting recognition (HWR), rely on grid based single character recognition, which forces users to print characters in stylized formats. This approach is not suitable for entering large text segments. A better approach for entering large text segments is to enable users to write naturally on the screen in their own personal, unconstructed style using HWR algorithms. However, HWR algorithms require a large amount of computation to translate handwritten symbols into machine readable characters. Typical portable pen-based computer systems lack the computational power necessary to satisfactorily perform translations.
Typical portable pen-based computer systems use a general purpose CPU for HWR calculations. Typically, a general purpose CPU is inefficient in power consumption during HWR calculations. The general purpose CPU is designed to perform more than HWR calculations, so some functions of the CPU are powered, but not used for the HWR calculation. Additionally, a general purpose CPU is inefficient in speed during HWR calculations. The general purpose CPU must be able to perform certain operating system tasks while completing HWR calculations. Thus, the speed with which HWR calculations are completed is diminished. As a result, fewer HWR calculations may be completed in a limited amount of time. Thus, if the time for HWR is limited, the accuracy of the translation is also limited.
Single Symbol Translation
Typically, portable pen-based computer systems translate one character at a time. However, such a scheme is difficult when a user has poor handwriting. For example, FIG. 1 illustrates a word where single symbol translation is difficult. A single symbol translation system has difficulty translating the letters “m” (100), “i” (110), and “n” (120) in the word “jumping” (130) in FIG. 1. However, the word is legible to the user.